/// 有理数と演算。要洗練
/// 自動的には約分しない
/// Date: September 9, 2008
module rational;
import bignum;
import std.string;

/// 有理数クラス
class Rational {
  int sign;  /// 符号。0か±1。
  int[] bunsi; /// 分子の絶対値
  int[] bunbo; /// 分母の絶対値(≠0)

  invariant() {
    assert(abschk(bunsi));
    assert(abschk(bunbo));
    assert(bunbo.length>0); //分母は0でない
    assert(bunsi.length>0 && (sign==1 || sign==-1) || sign==0);
  }

  /// 符号s, 分子a, 分母bで初期化（チェックなし）
  this(int s, int[] a, int[] b) {
    sign=s; bunsi=a; bunbo=b;
  }

  /// 約分して返す
  Rational yakubun() {
    if(sign==0) {
      return new Rational(0,[],[1]);
    }
    int[] d = absgcd(bunsi, bunbo);
    return new Rational(sign, absdiv(bunsi, d), absdiv(bunbo, d));
  }

  /// "符号 分子 / 分母"に変換
  override string toString() {
    string sgn = sign==-1 ? "- " : "";
    return sgn ~ tos(bunsi) ~ " / " ~ tos(bunbo);
  }

  /// 10進小数に（循環はカッコに囲って検出）
  string todec() {
    int[] r;
    int[] i=absdivmod(bunsi, bunbo, r); //整数部分
    int[] qs; //小数部分を1ケタずつ（<10)
    int[int[]] rs; //余りとあらわれたケタ

    int u=0;
    bool loop=false;
    while(r.length!=0) {
      rs[r]=u++;
      int[] q = absdivmod(absmul(r,toabs(10)), bunbo, r);
      assert(q.length==0 || (q.length==1 && 0<q[0] && q[0]<10));
      qs ~= q.length==0 ? 0 : q[0];
      if(r in rs) {
        u=rs[r];
        loop=true;
        break;
      }
    }

    string s = sign<0 ? "-" : "";
    s~=tos(i);
    if(qs.length>0) {
      s~=",";
      if(loop) {
        size_t k;
        for(; k<u; k++) s~=std.string.toString(qs[k]);
        s~="(";
        for(; k<qs.length; k++) s~=std.string.toString(qs[k]);
        s~=")";
      } else {
        foreach(n; qs) s~=std.string.toString(n);
      }
    }
    return s;
  }

  /// 小数点以下kケタで切捨て（kケタ未満の場合0を埋めたりしない）
  string todec(uint k) {
    int[] r;
    int[] i = absdivmod(bunsi, bunbo, r); //整数部分
    int[] qs; //小数部分をKケタずつ（<N)
  
    bool term = (r.length==0);
    for(uint k1=0; !term && k1<k; k1+=K) {
      int[] q = absdivmod([0]~r, bunbo, r);
      assert(q.length<=1);
      qs ~= q.length==0 ? 0 : q[0];
      term = (r.length==0);
    }

    static string fom;
    if(!fom) fom=format("%%0%dd", K);
    string s = sign<0 ? "-" : "";
    s~=tos(i);
    if(qs.length>0) {
      assert(k>0);
      s~=",";
      string t;
      foreach(n; qs) t~=format(fom,n);
      assert(t.length==qs.length*K);
      if(term) {
        assert(countchars(t[$-K..$],"1-9")>0);
        uint k1=t.length;
        while(t[k1-1]=='0') k1--;
        if(k1<k) k=k1;
      }
      t=t[0..k];
      s~=t;
    }
    return s;
  }

  /// 小数点以下kケタで四捨五入（〃）
  string todec_round(uint k) {
    // 基本方針は絶対値に1/(2*10^k)を足して切捨る
    int[] a = absmul(abspow(toabs(10), toabs(k)), [2]);
    int[] b = absadd(absmul(bunsi, a), bunbo);
    int[] c = absmul(bunbo, a);
    Rational r = new Rational(sign, b, c);
    string s=r.todec(k+1); // 1ケタ先まで求めて割り切れていたか判定する
    size_t i=s.length;
    while(i>0 && s[i-1]!=',') i--;
    uint sl = i ? s.length-i : 0; // 小数以下の長さ
    if(sl==k) {
      return s;
    } else if(sl<k) {
      if(sl==0) s~=",";
      for( ; sl<k; sl++) s~="0";
      return s;
    } else {
      assert(sl==k+1);
      if(s[$-1]=='5') { // もともと割り切れたいた
        int j=s.length-1;
        while(s[j-1]=='0') j--;
        return s[j-1]==',' ? s[0..j-1] : s[0..j];
      } else {
        return k ? s[0..$-1] : s[0..$-2];
      }
    }
  }
}

/// 足し算
Rational ratadd(Rational r1, Rational r2) {
  if(r1.sign==0) return r2;
  if(r2.sign==0) return r1;

  if(r1.sign==r2.sign) {
    return new Rational(r1.sign,
                        absadd(absmul(r1.bunsi, r2.bunbo), absmul(r2.bunsi, r1.bunbo)),
                        absmul(r1.bunbo, r2.bunbo));
  } else if(r1.sign>r2.sign) {
    Bignum b = abssub(absmul(r1.bunsi, r2.bunbo), absmul(r2.bunsi, r1.bunbo));
    return new Rational(b.sign, b.abs, absmul(r1.bunbo, r2.bunbo));
  } else {
    assert(r1.sign<r2.sign);
    Bignum b = abssub(absmul(r2.bunsi, r1.bunbo), absmul(r1.bunsi, r2.bunbo));
    return new Rational(b.sign, b.abs, absmul(r1.bunbo, r2.bunbo));
  }
}

/// 符号反転
Rational ratminus(Rational r) {
  return new Rational(-r.sign, r.bunsi, r.bunbo);
}

/// 引き算
Rational ratsub(Rational r1, Rational r2) {
  return ratadd(r1, ratminus(r2));
}

/// 掛け算
Rational ratmul(Rational r1, Rational r2) {
  if(r1.sign==0 || r2.sign==0) {
    return new Rational(0,[],[1]);
  } else {
    return new Rational(r1.sign*r2.sign, absmul(r1.bunsi, r2.bunsi), absmul(r1.bunbo, r2.bunbo));
  }
}

/// 逆数
Rational ratinv(Rational r) {
  if(r.sign==0) {
    throw new ZeroDivException();
  }
  return new Rational(r.sign, r.bunbo, r.bunsi);
}

/// 割り算
Rational ratdiv(Rational r1, Rational r2) {
  return ratmul(r1, ratinv(r2));
}

/// 大小比較
int ratcomp(Rational r1, Rational r2) {
  if(r1.sign>r2.sign) return 1;
  if(r1.sign<r2.sign) return -1;
  switch(r1.sign) {
    case 1:
      return abscomp(absmul(r1.bunsi, r2.bunbo), absmul(r2.bunsi, r1.bunbo));
    case -1:
      return abscomp(absmul(r2.bunsi, r1.bunbo), absmul(r1.bunsi, r2.bunbo));
    default:
      return 0;
  }
}

/// Rationalへの変換失敗。
class RatConvError : Error {
  this() { super("cannot convert to Rational!"); }
}

/// Rationalに変換 (tobigを呼び出す)
/// Throw: 変換失敗時RatConvError
Rational torat(T)(T n) {
  try {
    Bignum b=tobig(n);
  } catch(BigConvError e) {
    throw new RatConvError();
  }
  return new Rational(b.sign, b.abs, [1]);
}
